package com.jxb.test20241216;

import java.util.Arrays;

public class MergeSortedArray_88 {

    public static void main(String[] args) {
        int[] nums1  = {1,2,3,0,0,0};
        int[] nums2  = {2,5,6};
        System.out.println(Arrays.toString(mergeFastLessSpace(nums1,3,nums2,3)));;
    }

    //合并2个数组，然后再进行排序
    public static int[] mergeNormal(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i<n; i++) {
            nums1[m+i] = nums2[i];
        }
        //对数组进行排序
        Arrays.sort(nums1);
        return nums1;
    }

    //双指针-时间：O(m+n),空间：O(m+n)
    public static int[] mergeFast(int[] nums1, int m, int[] nums2, int n) {
        int[] res = new int[m+n];
        for (int index=0,i=0,j=0;index<(m+n);index++) {

            //num1没有元素了，直接从num2取
            if (i>=m) {
                res[index] = nums2[j++];
            }

            //num2没有元素了，直接从num1取
            else if (j>=n) {
                res[index] = nums1[i++];
            }

            else if (nums1[i] < nums2[j]) {
                res[index] = nums1[i++];
            }else {
                res[index] = nums2[j++];
            }
        }
        return res;
    }

    //双指针逆序处理：时间O(m+n)，空间O(1)
    public static int[] mergeFastLessSpace(int[] nums1, int m, int[] nums2, int n) {
        int k = m+n;
        for (int index=k-1,num1Index=m-1,num2Index=n-1; index >= 0; index--) {
            //数组2取完，就不用取了
            if (num2Index < 0 ) {
                break;
            }else if (num1Index < 0) {
                nums1[index] = nums2[num2Index--];
            } else if (nums1[num1Index] < nums2[num2Index]) {
                nums1[index] = nums2[num2Index--];
            }else {
                nums1[index] = nums1[num1Index--];
            }
        }
        return nums1;
    }

}
